As used herein in the specification and claims, "parity" is intended to connote parity as generated for use in redundant storage arrays, including exclusive OR (XOR) and other codes (e.g., the b-adjacent Reed-Solomon codes) that require only one data bit and the partial parity bit as modified on a data-block-by-data-block basis; and the parity generating code should use an associative and commutative calculation that is performed on a bit-by-bit basis within tile data blocks. Error Correction Code (ECC) is intended to connote use of conventional parity and ECC techniques for error detection and/or correction in memories. "Storage devices" is intended to include but not be limited to disk files, tape drives, optical disks, and cache memories "Data source" is intended to connote a channel interface, a memory, a storage device, a microprocessor on a bus, a bus-to-bus bridge, or any other device that can supply data to a bus.
The feasibility of redundant disk arrays is described by Patterson et al in "A case for redundant arrays of inexpensive disks", Report No. UCB/CSD 87/391, Computer Science Division, University of California/Berkeley, December 1987.
The advent of small form-factored disks and various design improvements have made it feasible to use "parity" devices in arrays of external storage devices (such as disk arrays). Key to making a parity device usable is minimizing the performance effects and resources required to calculate parity. Parity is normally calculated in a special dedicated parity generator that is connected to the main data bus of the array controller. In addition to bus controls and logic to control the parity generator, multiple passes of the data are required on the bus. For high data rate arrays, such as one able to support the rated bandwidth of a High Performance Parallel Interface (HPPI) input/output bus, the HPPI interface can handle 200 MB/sec. However, a worst case condition (e.g. a normal write coupled with a read, with one device out of service), would require a bandwidth of 800 MB/sec if the array uses a conventional parity generator; or without the parity generator, a bandwidth of 400 MB/sec.
U.S. Pat. No. 3,876,978 discloses a system comprising an array of tape drives and means, including a specially dedicated one of these tape drives, for preventing catastrophic loss of data in one of the remaining tape drives. The dedicated tape drive, in conventional fashion, stores, as check bits, the XOR summation of the bits of the other tape drives at each respective bit position. More specifically, information read from a tape is sent to a buffer, fed to a two-way XOR, buffered, and then written back on the tape. However, this system merely reads and writes (calculates) parity, and does not and cannot read and write data. It constitutes a dedicated resource that only generates parity for a plurality of tape drives. Moreover, this arrangement requires numerous data transfers and a parity calculation sequence that is fixed.
U.S. Pat. No. 3,976,982 discloses an apparatus for manipulating graphic images by reading a base image stored at one location in an accumulating memory, combining and XORing it with a sequence read from another raster source, and then writing the combined image in said memory at the same location. However, there is no teaching or suggestion that this approach be modified and used to create a new method for parity generation.
There is a need for an improved method and means for calculating and generating parity for external storage devices, such as disk arrays, which (1) permits a reduction in the bandwidth of the array controller bus and the number of data transfers required; (2) permits transfer of the parity blocks in any order and interspersed with other parity calculations; (3) permits each storage area in the memory to be used for data or parity, thereby simplifying system design, and (4) in addition to controlling the normal operations of the memory, responds to a special "write parity" signal to write parity.